/*
 * Fibonacci数列
 *
 * 题目链接：https://programming.pku.edu.cn/probset/6c33c406908948408786e82906caf024/220ee183a5a04b76b75cdd6c32b432d9/
 * 作者：lyazj <seeson@pku.edu.cn>
 *
 * 本题所需主要知识点：
 *   - 迭代
 *
 * 本题易错点：
 *   - 未正确判断迭代初始和终止条件
 *   - 未考虑数值溢出问题
 */

#include <iostream>
#include <iomanip>
#include <tuple>  // for std::tie()

using namespace std;

int main()
{
  int n;
  cin >> n;
  int f0 = 1, f1 = 1, f2;
  if(n == 1) {  // 其实这个分支可以省略，但我们可以留着让编译器来优化
    cout << f0 << endl;
  } else {
    for(int i = 2; i < n; ++i) {
      f2 = (f0 + f1) % 10000;  // 每步取模，避免溢出
      tie(f0, f1) = {f1, f2};  // 左引用，右拷贝
    }
    cout << f1 << endl;
  }
  return 0;
}

